Leetcode 98.验证二叉搜索树

题目描述：

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：

• 节点的左子树只包含小于当前节点的数。
• 节点的右子树只包含大于当前节点的数。
• 所有左子树和右子树自身必须也是二叉搜索树。

示例 1:

1
2
3
4
5

输入:
    2
   / \
  1   3
输出: true

示例 2:

1
2
3
4
5
6
7
8
9

输入:
    5
   / \
  1   4
     / \
    3   6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
     根节点的值为 5 ，但是其右子节点值为 4 。

链接：

https://leetcode-cn.com/problems/validate-binary-search-tree

题目分析

  我们知道二叉搜索树按照中序遍历的话得到的一定是升序序列。则我们根据中序遍历检查是否满足升序序列即可。我们维护了一个 pre 表示已经遍历过的最后一个结点的值，而当前结点的值必须大于 pre，出现不满足的结点则可以直接返回 false。遍历完这个结点后，我们更新 pre 的值为当前结点值。
  注意到题目中结点值 val 是 int 类型的，最小可以达到 INT_MIN（测例中真的有一个 INT_MIN）。我们设置的哨兵值要比这个值还小，因此采用了 long 类型，并赋初始值为 LONG_MIN。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution {
    bool inorder(TreeNode* root, long& pre){
        if(root){
            if(!inorder(root->left, pre)) return false;
            if(root->val <= pre) return false;
            pre = root->val;
            if(!inorder(root->right, pre)) return false;
        }
        return true;
    }
public:
    bool isValidBST(TreeNode* root) {
        long pre = LONG_MIN;
        return inorder(root, pre);
    }
};

  时间复杂度：$O(n)$，其中 $n$ 为二叉搜索树的结点数。我们最多对二叉搜索树进行了一次中序遍历。
  空间复杂度：$O(n)$，其中 $n$ 为二叉搜索树的结点数。也即递归栈的深度，而当二叉树是一条链时，最大深度为 $n$。